package cn.kent.simple;

/**
 * 53. 最大子数组和
 * todo: 分治方法待补充
 */
public class MaxSubArray {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        // int[] nums = {-1};
        // int[] nums = {5,4,-1,7,8};
        int i1 = maxSubArray(nums);
        System.out.println("i1：" + i1);
        int i = maxSubArray2(nums);
        System.out.println("i：" + i);
    }

    /**
     * 常规解法
     * 思路1：两层循环，计算值，找到最大的。 ==> 最后错误是因为给了一个超长数组导致超时了
     */
    private static int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        if (nums.length == 0) return 0;
        for (int i = 0; i < nums.length; i++) { // 外层循环 - 遍历
            int sum = 0;
            for (int j = i; j < nums.length; j++) {// 内层循环 - 计算
                sum += nums[j];
                if (sum > max) {
                    max = sum;
                }
            }
        }
        return max;
    }

    /**
     * 常规解法 - 滚动数组
     * 思路2：前面的加起来还没有当前的数大，就只保留当前的
     * 时间复杂度分析：O(n)
     * 2ms | 1ms
     */
    private static int maxSubArray2(int[] nums) {
        int maxAns = nums[0], pre = 0;
        for (int num : nums) {
            pre = Math.max(pre + num, num); // 将前面+当前的和当前的比大小，大的赋值给pre
            maxAns = Math.max(maxAns, pre); // 将maxAns和pre比大小，这一步实现了==>将[前面+当前] 和 [前面] 比大小。
        }
        return maxAns;
    }
}
